package com.mlh.dp.knapsackProblem;

// 分割等和子集
// 给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
// 输入：nums = [1,5,11,5]
// 输出：true
// 解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

public class CanPartition {
    public static void main(String[] args) {
        int []nums={1,2,5};
        System.out.println(method1(nums));

    }
    public static boolean method1(int[]nums){
        int a=0;
        for(int temp:nums){
            a+=temp;
        }
        if(a%2!=0){
            return false;
        }
        int bag=a>>1;

        boolean[]dp=new boolean[bag+1];
        dp[0]=true;
        //这边被我优化了  原本是二维dp  但这里是可以降低为1维的
        for(int i=0;i<nums.length;i++){
            for(int j=bag;j>=0;j--){
                if(j>=nums[i]){
                    dp[j]=dp[j-nums[i]]|dp[j];
                }
            }
        }
        return dp[bag];
    }

    //我先写了递归版本  后面才写得出来严格表依赖  感觉还是差点东西
    public static boolean process(int[]nums,int bag,int end){
        if(end==nums.length){
            return bag==0?true:false;
        }
        if(bag<=0){
            return bag==0?true:false;
        }
        if(process(nums,bag-nums[end],end+1)||process(nums,bag,end+1)){
            return true;
        }
        return false;
    }


}
